package 算法;

import com.sun.xml.internal.bind.v2.runtime.unmarshaller.XsiNilLoader;
import testJ.S;

import java.util.*;
class Node1{
    int val;
    Node1 next;
    Node1 random;

    public Node1(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
class LRUCache {
    HashMap<Integer,Integer> val = new HashMap<>();
    HashMap<Integer,Integer> life = new HashMap<>();
    int len = 0;
    public LRUCache(int capacity) {
        len = capacity;
    }

    public int get(int key) {
        for (Integer integer : life.keySet()) {
            if(key != integer)
                life.put(integer,life.get(integer)+1);
        }
        return val.get(key);
    }

    public void put(int key, int value) {
        if(val.size() == len){
            //满了，需要删除在插入
            Integer k1 = new Integer(0);
            Integer max = new Integer(0);
            for (Integer integer : life.keySet()) {
                if(life.get(integer) > max){
                    k1 = integer;
                    max = life.get(integer);
                }
            }
            val.remove(k1);
            life.remove(k1);

        }else {
            val.put(key,value);
            for (Integer integer : life.keySet()) {
                life.put(integer,life.get(integer)+1);
            }
            life.put(key,0);
            
        }
    }
}
public class 动态规划 {
    public static void main(String[] args) {
//        LRUCache lRUCache = new LRUCache(2);
//        lRUCache.put(1, 1); // 缓存是 {1=1}
//        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
//        lRUCache.get(1);    // 返回 1
//        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
//        lRUCache.get(2);    // 返回 -1 (未找到)
//        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
//        lRUCache.get(1);    // 返回 -1 (未找到)
//        lRUCache.get(3);    // 返回 3
//        lRUCache.get(4);    // 返回 4
//        new 动态规划().allCellsDistOrder(3,3,0,0);
//        new 动态规划().getMaxMatrix(new int[][]{{9,-8,1,3,-2},{-3,7,6,-2,4},{6,-4,-4,8,-7}});
//        deleteAndEarn(new int[]{8,7,3,8,1,4,10,10,10,2});
        System.out.println(shui(new int[]{1,2}));
    }
    public int trap(int[] height) {
        return 0;
    }
    public static int shui(int[] height){
        int i = -1;
        int res = 0;
        while (i < height.length-1){
            if(height[++i] != 0) break;
        }
        if(i == height.length) return res;
        while (i < height.length-1){
            int j = i;
            while (i < height.length-1){
                if(height[++i] != 0) break;
            }
            if(i == height.length) return res;
            res += i-j-1;
        }
        return res;
    }
    public static int deleteAndEarn(int[] nums) {
       int[] val = new int[10001];
        for (int num : nums) {
            val[num]+=num;
        }
        int v = val.length;
        int tt = val[0];
        int tvs = val[1];
        int res = tvs;
        for (int i = 2; i < v; i++) {
            res = tt+val[i] > tvs?  tt+val[i]:tvs;
            tt=tvs;
            tvs=res;
        }
        return res;
    }
    public static int rob(int[] nums) {
        int len = nums.length;
        int[] db = new int[len];
        db[0]=0;db[1]=nums[1];
        for (int i = 2; i < len; i++) {
            db[i] = nums[i]+db[i-2]>db[i-1]?nums[i]+db[i-2]:db[i-1];
        }
        int res = db[len-1];
        db[len-1]=0;
        db[len-2]=nums[len-2];
        for(int i = len-3;i >= 0;i--){
            db[i] = nums[i]+db[i+2] > db[i+1]?nums[i]+db[i+2]:db[i+1];
        }
        return res > db[0] ? res:db[0];
    }

    //最大子矩阵和
    public int maxSumSubmatrix(int[][] matrix, int k) {
        return 0;
    }
    public static int[] getMaxMatrix(int[][] matrix) {
        int[] res = new int[4];
        int sum = Integer.MIN_VALUE;

        int x = matrix.length;
        int y = matrix[0].length;

        int[] dp = new int[y];

        for (int i = 0; i < x; i++) {
            for (int i1 = 0; i1 < dp.length; i1++) {
                dp[i1] = 0;
            }
            for(int j = i;j < x; j++){
                for(int k = 0; k < y;k++){
                    dp[k] += matrix[j][k];
                }
                //最长子序列
                int begin =0;

                int cureenMax = 0;
                for (int i1 = 0; i1 < dp.length; i1++) {
                    if(cureenMax > 0){
                        cureenMax = cureenMax+dp[i1];
                    }else {
                        cureenMax = dp[i1];
                        begin = i1;
                    }
                    if(cureenMax > sum){
                        res[0] = i;
                        res[1] = begin;
                        res[2] = j;
                        res[3] = i1;
                        sum = cureenMax;
                    }
                }
            }
        }

        return res;
    }
    class Arr{
        int val;
        int x,y;

        public Arr(int val, int x, int y) {
            this.val = val;
            this.x = x;
            this.y = y;
        }
    }
    //最小是负200
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int[][] res = new int[R][C];

        int[][] val = new int[R*C][2];
        int i = 0;

        res[r0][c0] = -(R+C);
        Queue<int[]> stack1 = new LinkedList<>();
        stack1.add(new int[]{r0,c0});

        while (!stack1.isEmpty()){
            int[] te = stack1.poll();
            val[i][0] = te[0];
            val[i++][1] = te[1];
            int r = res[te[0]][te[1]]+1;
            if(te[0]+1 < R && res[te[0]+1][te[1]] > r){
                res[te[0]+1][te[1]] = r;
                stack1.add(new int[]{te[0]+1,te[1]});
            }
            if(te[0]-1 >= 0 && res[te[0]-1][te[1]] > r){
                res[te[0]-1][te[1]] = r;
                stack1.add(new int[]{te[0]-1,te[1]});
            }


            if(te[1]+1 < C && res[te[0]][te[1]+1] > r){
                res[te[0]][te[1]+1] = r;
                stack1.add(new int[]{te[0],te[1]+1});
            }
            if(te[1]-1 >= 0 && res[te[0]][te[1]-1] > r){
                res[te[0]][te[1]-1] = r;
                stack1.add(new int[]{te[0],te[1]-1});
            }
        }

        return val;
        }

    public void inited(int[][] R,int r0,int c0){


        int r = R[r0][c0]+1;
        if(r0+1 < R.length && R[r0+1][c0] > r){
            R[r0+1][c0] = r;
            inited(R,r0+1,c0);
        }
        if(c0+1 < R[0].length && R[r0][c0+1] > r){
            R[r0][c0+1] = r;
            inited(R,r0,c0+1);
        }
        if(r0-1 >= 0 && R[r0-1][c0] > r){
            R[r0-1][c0] = r;
            inited(R,r0-1,c0);
        }
        if(c0-1 >= 0 && R[r0][c0-1] > r){
            R[r0][c0-1] = r;
            inited(R,r0,c0-1);
        }
    }
    public Node1 copyRandomList(Node1 head) {
        HashMap<Node1,Node1> hashMap = new HashMap<>();
        Stack<Node1> stack1 = new Stack<>();
        Stack<Node1> stack2 = new Stack<>();
        Node1 res = new Node1(head.val);
        stack1.push(head);
        stack2.push(res);
        while (!stack1.isEmpty()){
            Node1 node1 = stack1.pop();
            Node1 node2 = stack2.pop();
            Node1 temp;
            if(hashMap.containsKey(node1.next)){
                node2.next = hashMap.get(node1.next);
            }else {
                temp = new Node1(node1.next.val);
                node2.next = temp;
                stack1.push(node1.next);
                stack2.push(temp);
            }
            if(node1.random == node1) node2.random = node2;
            if(hashMap.containsKey(node1.random)){
                node2.random = hashMap.get(node1.random);
            }else {
                temp = new Node1(node1.random.val);
                node2.random = temp;
                stack1.push(node1.random);
                stack2.push(temp);
            }
            hashMap.put(node1,node2);
        }
        return res;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList();
        Queue<TreeNode> temp1 = new LinkedList<>();
        Queue<TreeNode> temp2 = new LinkedList<>();
        temp1.add(root);
        List<Integer> re;
        while (!temp1.isEmpty()){
            re = new ArrayList<>();
            while (!temp1.isEmpty()){
                TreeNode temp = temp1.poll();
                re.add(temp.val);
                if(temp.left != null)
                    temp2.add(temp.left);
                if(temp.right != null)
                    temp2.add(temp.right);

            }
            res.add(re);
            Queue temps1 = temp1;
            temp1 = temp2;
            temp2 = temps1;
        }
        return res;
    }
    public int maxSubarraySumCircular(int[] A) {
        int len = A.length;
        if (len == 1) return A[0];
        int[] left = new int[len];
        int[] right = new int[len];
        int max;
        left[0] = A[0];
        max = left[0];
        for (int i = 1; i < left.length; i++) {
            left[i] = A[i] > left[i-1]+A[i] ?A[i]:left[i-1]+A[i];
            max = max>left[i] ? max:left[i];
        }
        right[len-1]=A[len-1];
        for (int i = right.length - 2; i >= 0; i--) {
            right[i] = A[i] > right[i+1]+A[i] ?A[i]:right[i+1]+A[i];
            max = max > right[i] ? max:right[i];
        }
        for (int i = 0; i < left.length; i++) {
            for (int i1 = right.length - 1; i1 > i; i1--) {
                max = max > left[i]+right[i1] ? max:left[i]+right[i1] ;
            }
        }
        return max;
    }
    public int maxProduct(int[] nums) {
        //0最大正，1最大负
        int[][] max = new int[nums.length][2];
        max[0][0] = max[0][1] = nums[0];
        int[] temp = new int[3];
        int te1,te2;
        for (int i = 1; i < nums.length; i++) {
            temp[0] = nums[i];
            temp[1] = nums[i]*max[i-1][0];
            temp[2] = nums[i]*max[i-1][1];
            te1=te2=temp[0];
            for (int i1 : temp) {
                te1 = i1 > te1 ?i1:te1;
                te2 = i1 < te2 ? i1:te2;
                max[i][0] = te1;
                max[i][1] = te2;
            }
        }
        te1 = max[0][0];
        for (int[] ints : max) {
            te1 = ints[0]>te1?ints[0]:te1;
        }
        return te1;
    }
    public int maxSubArray(int[] nums) {
        int len = nums.length;

        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i-1]+nums[i]>nums[i] ? nums[i-1]+nums[i]:nums[i];
        }
        int max = nums[0];
        for (int num : nums) {
            max = max >num?max:num;
        }
        return max;
    }
    public int rob1(int[] nums) {
        int len = nums.length;
        if(len==0)return 0;
        if(len < 2)return nums[0];
        int[] res = new int[len];
        res[0] = nums[0];
        res[1] = nums[0] > nums[1] ? nums[0]:nums[1];
        for (int i = 2; i < len; i++) {
            res[i] = nums[i]+res[i-2] > res[i-1] ? nums[i]+res[i-2]:res[i-1];
        }
        return res[len-1];
    }
    public int maxEnvelopes(int[][] envelopes) {
        int len = envelopes.length;
        if(len == 0){
            return 0;
        }
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] ints, int[] t1) {
                if(ints[0] > t1[0]){
                    return 1;
                }else if(ints[0] == t1[0] && ints[1] > t1[1]){
                    return 1;
                }
                return -1;
            }
        });

        int[] res = new int[len];
        res[0] = 1;
        for (int i = 1; i < res.length; i++) {
            for (int i1 = i-1; i1 > 0; i1--) {
                if(envelopes[i][0] > envelopes[i1][0] && envelopes[i][1] > envelopes[i1][1]){
                    break;
                }
            }
        }
        int max = 0;
        for (int re : res) {
            max = max > re ? max:re;
        }
        return max;

    }
}
